package primary.primary0;

import java.util.Arrays;

/**
 *
 */
public class S0322零钱兑换 {




    /**
     * 超时, 这里是深度优先, 其实按照他找最小组合的想法, 应该用广度优先
     * 很好玩的一点是, 按照最大的开始减少, 找到的第一个成功的组合并不一定是最优解, 比如[10, 9, 1] amout 48, 这种。
     * 那么就还是要遍历每一个情况。
     */
    // 不需要一个数组来记每一次的大小, 只需要一个数值来维护一个最小值就行。
    // public List<Integer> coinSumRecord = new ArrayList<>();
    public int minSum = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        coinChangeHelper(coins, amount, 0);
        return minSum == Integer.MAX_VALUE? -1 : minSum;
    }

    // 回溯, 搞不好会爆, 直接调用自己, 减一个coin种类传下去
    public void coinChangeHelper(int[] coins, int amount, int curSumNum) {
        if(curSumNum >= minSum){
            return ;
        }
        int totalLength = coins.length;
        if(amount == 0){
            System.out.println(curSumNum);
            minSum = curSumNum;
            return;
        }
        if(totalLength == 0){
            return;
        }
        for(int curCoinNum = amount / coins[totalLength - 1]; curCoinNum >= 0; curCoinNum --){
            //System.out.println("当前coin大小 " + coins[totalLength - 1] + " 数量 " + curCoinNum);
            coinChangeHelper(Arrays.copyOfRange(coins, 0, totalLength - 1),
                    amount - coins[totalLength - 1] * curCoinNum, curSumNum + curCoinNum);
        }
    }

    public static void main(String[] args) {
        S0322零钱兑换 s0322零钱兑换 = new S0322零钱兑换();
        int[] coins = new int[]{411,412,413,414,415,416,417,418,419,420,421,422};
        System.out.println(s0322零钱兑换.coinChange(coins, 9864));
    }
}
